package ljl.alg.wangzheng_camp.round1.hashmap;

import java.util.*;

/**
 * 这个简单题居然有点小拐弯
 *
 * */
public class _1122_relative_sort {
    
    /*
    * 先 arr2 建立一个 hashtable
    * 遍历 arr1，如果 2 里有，放进去
    * 否则，放到一个 list 里
    * 排序这个 list，放到 arr1 的末尾
    *
    * 错哪了？要以 2 的顺序来排 1
    *
    * 那是不是得把 1 里的全都分组了，看来是的
    *
    * 看了答案，发现我的思路偏离了出题人意图
    *
    * */
    public int[] relativeSortArray33333(int[] arr1, int[] arr2) {
        List<Integer> notContained = new ArrayList<>();
        HashMap<Integer, Integer> map1 = new HashMap<>();
        Set<Integer> set2 = new LinkedHashSet<>();
        
        for (int i : arr2) {
            set2.add(i);
        }
        for (int i : arr1) {
            if (set2.contains(i))
                map1.put(i, map1.getOrDefault(i, 0) + 1);
            else
                notContained.add(i);
        }
    
        int i = 0;
        for (Integer each : set2) {
            int count = map1.get(each);
            for (int j = 0; j < count; j++) {
                arr1[i++] = each;
            }
        }
        notContained.sort(Comparator.naturalOrder());
        for (int each : notContained) {
            arr1[i++] = each;
        }
        return arr1;
    }
    
    // 基于自定义排序规则
    // 这种排序对 java 很不友好
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> dic = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            dic.put(arr2[i], i);
        }
        List<Integer> list = new ArrayList<>(arr1.length);
        for (int i : arr1) {
            list.add(i);
        }
        
        list.sort((a, b) -> {
            if (dic.containsKey(a) && dic.containsKey(b)) {
                return dic.get(a).compareTo(dic.get(b));
            }
            if (dic.containsKey(a)) return -1;
            if (dic.containsKey(b)) return 1;
            return a.compareTo(b);
        });
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = list.get(i);
        }
        return arr1;
    }
    /* python 的比较简单了，可以直接对 pair 进行排序
    *  雀食优雅！
    *
    * def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    *   def cmp(x: int) -> (int, int): return (0, rank[x]) if x in rank else (1, x)
    *
    *   rank = {x: i for i, x in enumerate(arr2)}
    *   arr1.sort(key = cmp)
    *   return arr1
    * */
    
    /*
    * 什么？还能优化？是的！由于数值全是正数，所以可以不使用 tuple，利用 rank[x] - n 代替 (0, rank[x])，x 代替 (1, x)
    * 前者必定负数，后者必定正数
    * def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
    *   def cmp(x: int): return rank[x] if x in rank else x
    *
    *   n = len(arr2)
    *   rank = {x: i - n for i, x in enumerate(arr2)}
    *   arr1.sort(key = cmp)
    *   return arr1
    * */
    
    /*
    * 这个解法和我的解法很像，所以不必急着妄自菲薄
    * 这个居然还很快
    * */
    public int[] relativeSortArray_official(int[] arr1, int[] arr2) {
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        int[] frequency = new int[upper + 1];
        for (int x : arr1) {
            ++frequency[x];
        }
        int[] ans = new int[arr1.length];
        int index = 0;
        for (int x : arr2) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
            frequency[x] = 0;
        }
        for (int x = 0; x <= upper; ++x) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
        }
        return ans;
    }
    
    /**
     * 我模仿上面的官方解法：
     *
     * 声明完 freqs 就开始用
     * 真牛逼啊你
     * */
    public int[] relativeSortArray4(int[] arr1, int[] arr2) {
        int upper = 0;
        for (int i : arr1) {
            if (i > upper) upper = i;
        }
        int[] freqs = new int[upper + 1];
        for (int i : arr1) {
            freqs[i]++;
        }
        int i = 0;
        for (int j : arr2) {
            for (int k = 0, c = freqs[j]; k < c; k++) {
                arr1[i++] = j;
            }
            freqs[j] = 0;
        }
        for (int j = 0; j <= upper; j++) {
            for (int k = 0, c = freqs[j]; k < c; k++) {
                arr1[i++] = j;
            }
        }
        return arr1;
    }
    
}
